package com.sx.sx1.lintcode.day717;

import java.util.ArrayList;
import java.util.List;

public class LC206 {


    static class Interval {
          int start, end;
          Interval(int start, int end) {
              this.start = start;
              this.end = end;
          }
      }


    static class Solution {
        /**
         * @param a: An integer list
         * @param queries: An query list
         * @return: The result list
         */
        public List<Long> intervalSum(int[] a, List<Interval> queries) {
            SegmentNode root = build(a,0,a.length-1);
            List<Long> ans = new ArrayList<>();
            for (Interval v : queries) {
                ans.add(getsum(root,v.start,v.end));
            }
            return ans;
        }

        public long getsum(SegmentNode root,int start,int end){
            if(root.start >= start && end >= root.end)
                return root.sum;

            int m = root.start+(root.end-root.start)/2;
            long left =0,right =0;

            if(m>=start){
                left = getsum(root.left,start,Math.min(m,end));
            }

            if(m<end){
                right = getsum(root.right,m>=start?m+1:start,end);
            }
            return left+right;
        }


        public SegmentNode build(int[] arr,int start,int end){ //创建线段树
            if(start ==end){
                return new SegmentNode(start,end,arr[start]);
            }
            SegmentNode root = new SegmentNode(start,end,0);
            int m = start+(end-start)/2;
            root.left = build(arr,start,m);
            root.right = build(arr,m+1,end);
            root.sum = root.left.sum+root.right.sum;
            return root;
        }

        static class SegmentNode{ //线段树节点定义
            public int start,end;
            public long sum;
            public SegmentNode left,right;
            public SegmentNode(int s,int e,long s1){
                start =s;
                end =e;
                sum =s1;
            }
        }
    }

    public static void main(String[] args) {
        Solution  obj = new Solution();
        int[] arr = {1,2,7,8,5};
        List<Interval> queries = new ArrayList<>();
        queries.add(new Interval(0,4));
        queries.add(new Interval(1,2));
        queries.add(new Interval(2,4));

        System.out.println(obj.intervalSum(arr,queries));
    }

}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有184条未读消息，请及时查看
206 · 区间求和 I
算法
中等
通过率
36%

题目
题解21
笔记
讨论99+
排名
记录
描述
给定一个整数数组（下标由 0 到 n-1，其中 n 表示数组的规模），以及一个查询列表。每一个查询列表有两个整数 [start, end] 。 对于每个查询，计算出数组中从下标 start 到 end 之间的数的总和，并返回在结果列表中。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


在做此题前，建议先完成以下三题：线段树的构造， 线段树的查询，以及线段树的修改。

样例
样例 1:

输入: 数组 = [1,2,7,8,5], 查询 = [(0,4),(1,2),(2,4)]
输出: [23,9,20]
样例 2:

输入: 数组 = [4,3,1,2],  查询 = [(1,2),(0,2)]
输出: [4,8]
挑战
每一次查询的时间复杂度为O(logN)

相关知识
学习《 高级数据结构：线段树、树状数组》课程中的2.1线段树解决实战面试题1 Interval Sum相关内容 ，了解更多相关知识！
标签
相关题目

205
区间最小数
中等

207
区间求和 II
困难
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
已开启智能提示
发起考试
30 分 00 秒
123456789101112131415161718192021
}
控制台
历史提交

 */
